﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using KLadderProposal.Interfaces;
using KLadderProposal.Interfaces.BasicStructures;

namespace KLadderProposal.Algorithms
{
    public class CliqueFourAlgorithm : IAlgorithm
    {
        #region Fields (1)

        private const int CliqueSize = 4;

        #endregion Fields

        #region Methods (11)

        // Public Methods (1) 

        public void Run(IGraph graph)
        {

            int clsturNumber = 1;
            while (true)
            {
                HashSet<GraphNode> clique = new HashSet<GraphNode>();
                if (!FindCliqueInGraph(graph, clique, CliqueSize))
                    return;
                if (clique.Count != 4)
                {
                    Console.WriteLine("maybe have bug in FindCliqueInGraph");
                    Debugger.Break();
                }
                foreach (GraphNode graphNode in clique)
                {
                    if (graphNode.IsMarkedAsDeleted)
                        Console.WriteLine("maybe have bug in FindCliqueInGraph");
                }
                ExpandToCluster1(clique, CliqueSize, clsturNumber);
                clsturNumber++;
            }
        }
        // Private Methods (10) 

        private HashSet<GraphNode> Contiens(SortedList<string, GraphNode> neighbors, HashSet<GraphNode> subClique,
                                             int size)
        {
            int i = 0;
            HashSet<GraphNode> nodes = new HashSet<GraphNode>();

            foreach (KeyValuePair<string, GraphNode> item in neighbors)
            {
                if (subClique.Contains(item.Value) &&
                    !item.Value.IsMarkedAsDeleted)
                {
                    i++;
                    nodes.Add(item.Value);
                }
                if (i == size)
                    return nodes;
            }
            return nodes;
        }

        private void ExpandClique(HashSet<GraphNode> clique, Dictionary<string, HashSet<GraphNode>> cliques, int size)
        {

            foreach (GraphNode C in clique)
            {
                HashSet<GraphNode> subClique = new HashSet<GraphNode>();
                foreach (GraphNode item in clique)
                {
                    if (item.Label == C.Label)
                        continue;
                    subClique.Add(item);
                }

                foreach (GraphNode E in C.Neighbors.Values)
                {
                    if (C.Label == E.Label)
                        continue;
                    if (E.IsMarkedAsDeleted)
                        continue;

                    HashSet<GraphNode> results = Contiens(E.Neighbors, subClique, size - 2); //find 2 nodes from clique
                    if (results.Count == size - 2)
                    {
                        results.Add(E);
                        results.Add(C);
                        string key = GetHashSetKey(results);

                        //may be same node in list for this reson used hash set
                        //if results2.Count!=size the same node in results so skip
                        if (results.Count != size)
                        {
                            continue;
                        }
                        if (!cliques.ContainsKey(key))
                        {
                            bool found = results.Any(c => c.IsMarkedAsDeleted);
                            if (found)
                                continue;
                            if (clique.Count != 4)
                            {
                                Console.WriteLine("Error");
                                Debugger.Break();
                            }

                            cliques.Add(key, results);
                            Console.WriteLine("Clique,{0},CliqueCount,{1}", key, cliques.Count);
                        }
                    }
                    //    if (results.Count == size - 3)
                    //    {
                    //        foreach (GraphNode F in E.Neighbors.Values)
                    //        {
                    //            //find 1 node from clique,so try to find one more Neighbors
                    //            HashSet<GraphNode> results2 = Contiens(F.Neighbors, subClique, size - 2);

                    //            if (results2.Count == size - 3)
                    //            {
                    //                results2.Add(C);
                    //                results2.Add(E);
                    //                results2.Add(F);
                    //                //may be same node in list for this reson used hash set
                    //                //if results2.Count!=size the same node in results so skip
                    //                if (results2.Count != size)
                    //                {
                    //                    continue;
                    //                }
                    //                string key = GetHashSetKey(results2);

                    //                if (!cliques.ContainsKey(key))
                    //                {
                    //                    bool found = results.Any(c => c.IsMarkedAsDeleted);
                    //                    if (results2.Count != 4)
                    //                    {
                    //                        Console.WriteLine("Error");
                    //                        Debugger.Break();
                    //                    }
                    //                    if (found)
                    //                        continue;

                    //                    cliques.Add(key, results2);
                    //                    Console.WriteLine("Clique,{0},CliqueCount,{1}", key, cliques.Count);
                    //                    break;
                    //                }
                    //            }
                    //        }
                    //    }
                }
            }
        }

        private void ExpandToCluster(HashSet<GraphNode> clique, int size, int clusterNumber)
        {
            int count = 0;
            Dictionary<string, HashSet<GraphNode>> cliques = new Dictionary<string, HashSet<GraphNode>>();
            string key = GetHashSetKey(clique);
            cliques.Add(key, clique);

            HashSet<GraphNode> workingClique;
            int iterationNumber = 0;
            while (iterationNumber < cliques.Count)
            {
                workingClique = cliques.ElementAt(iterationNumber).Value;
                ExpandClique(workingClique, cliques, size);
                iterationNumber++;
            }
            foreach (HashSet<GraphNode> item in cliques.Values)
            {
                foreach (GraphNode graphNode in item)
                {
                    if (!graphNode.IsMarkedAsDeleted)
                    {
                        //Console.WriteLine("Maybe have bug in ExpandClique");

                        count++;
                        graphNode.IsMarkedAsDeleted = true;
                        graphNode.ClusterNumber = clusterNumber;
                    }
                }
            }
            Console.WriteLine("Cluster Add number,{0},Cluster size,{1}", clusterNumber, count);
        }

        private void ExpandToCluster1(HashSet<GraphNode> clique, int size, int clusterNumber)
        {
            Dictionary<string, GraphNode> list = new Dictionary<string, GraphNode>();//;<string, GraphNode>();

            foreach (var graphNode in clique)
            {
                list.Add(graphNode.Label, graphNode);
            }

            int iterationNumber = 0;
            while (iterationNumber < list.Count)
            {
                int i = 0;
                KeyValuePair<string, GraphNode> C = list.ElementAt(iterationNumber);
                foreach (KeyValuePair<string, GraphNode> E in C.Value.Neighbors)
                {
                    if (!IsPartOfClique(list, C, E)) continue;
                    if (!list.ContainsKey(E.Key))
                    {
                        list.Add(E.Key, E.Value);
                    }
                    // break;
                }
                iterationNumber++;

            }

            foreach (KeyValuePair<string, GraphNode> keyValuePair in list)
            {
                keyValuePair.Value.IsMarkedAsDeleted = true;
                keyValuePair.Value.ClusterNumber = clusterNumber;
            }
        }

        private bool FindCliqueInGraph(IGraph graph, HashSet<GraphNode> clique, int cliqueSize)
        {
            HashSet<GraphNode> commonNeigbors;

            //int maxNeigborsCount = graph.Nodes.Max(node => node.Neighbors.Count);
            //GraphNode nodeWithMaxNeigbors = graph.Nodes.First(node => node.Neighbors.Count == maxNeigborsCount );

            foreach (GraphNode nodeWithMaxNeigbors in graph.Nodes)
            {
                if (nodeWithMaxNeigbors.IsMarkedAsDeleted)
                {
                    continue;
                }
                foreach (GraphNode node in graph.Nodes)
                {
                    if (node.IsMarkedAsDeleted)
                    {
                        continue;
                    }
                    if (node == nodeWithMaxNeigbors)
                        continue;

                    if (GetCommonNeigborsCount(node, nodeWithMaxNeigbors, out commonNeigbors) < cliqueSize - 2) continue;

                    commonNeigbors.Add(node);
                    commonNeigbors.Add(nodeWithMaxNeigbors);

                    foreach (GraphNode commonNeigbor in commonNeigbors)
                    {
                        foreach (GraphNode node1 in commonNeigbors)
                        {
                            if (commonNeigbor == node1)
                                continue;
                            foreach (GraphNode node2 in commonNeigbors)
                            {
                                if (node2 == node1 || node2 == commonNeigbor)
                                    continue;
                                foreach (GraphNode node3 in commonNeigbors)
                                {
                                    if (node3 == node1 || node3 == commonNeigbor || node3 == node2)
                                        continue;
                                    if (!UtilesIsNeighbors(commonNeigbor, node2, node3, node1)) continue;
                                    clique.Add(commonNeigbor);
                                    clique.Add(node1);
                                    clique.Add(node2);
                                    clique.Add(node3);
                                    return true;
                                }
                            }
                        }
                    }
                }
            }

            return false;
        }

        private int GetCommonNeigborsCount(GraphNode graphNode, GraphNode neighbor,
                                           out HashSet<GraphNode> commonNeigbors)
        {
            commonNeigbors = new HashSet<GraphNode>();
            int commonNeighborsCount = 0;
            int i = 0, j = 0;

            while (i < graphNode.Neighbors.Count && j < neighbor.Neighbors.Count)
            {
                if (graphNode.Neighbors.Values[i].IsMarkedAsDeleted ||
                    neighbor.Neighbors.Values[j].IsMarkedAsDeleted)
                {
                    i++;
                    j++;
                    continue;
                }
                string label1 = graphNode.Neighbors.Values[i].Label;
                string label2 = neighbor.Neighbors.Values[j].Label;


                int comparisonResult = String.Compare(label1, label2, StringComparison.Ordinal);
                if (comparisonResult == 0)
                {
                    commonNeighborsCount++;
                    commonNeigbors.Add(neighbor.Neighbors.Values[j]);
                    i++;
                    j++;
                }
                else if (comparisonResult > 0)
                    j++;
                else
                    i++;
            }

            return commonNeighborsCount;
        }

        private string GetHashSetKey(HashSet<GraphNode> clique)
        {
            int size = clique.Count;
            string[] stamp = new string[size];
            int index = 0;

            foreach (GraphNode item2 in clique)
            {
                stamp[index] = item2.Label;
                index++;
            }

            Array.Sort(stamp);
            return string.Join(",", stamp);
        }

        private bool IsPartOfClique(Dictionary<string, GraphNode> list, KeyValuePair<string, GraphNode> C, KeyValuePair<string, GraphNode> E)
        {
            foreach (var A in E.Value.Neighbors)
            {
                if (A.Value.IsMarkedAsDeleted ||
                    A.Key == C.Key ||
                    !list.ContainsKey(A.Key))
                    continue;
                foreach (var B in E.Value.Neighbors)
                {
                    if (B.Value.IsMarkedAsDeleted ||
                         A.Key == B.Key ||
                           C.Key == B.Key ||
                    !list.ContainsKey(B.Key))
                        continue;

                    if (UtilesIsNeighbors(A.Value, B.Value, C.Value, E.Value))
                        return true;
                }
            }
            return false;
        }

        private bool UtilesIsNeighbors(GraphNode node1, GraphNode node2, GraphNode node3, GraphNode node4)
        {
            bool findNode2 = false, findNode3 = false, findNode4 = false;
            if (node1 == node2 ||
                node1 == node3 ||
                node1 == node4 ||
                node2 == node3 ||
                node2 == node4 ||
                node3 == node4)
                return false;
            foreach (KeyValuePair<string, GraphNode> neighbor in node1.Neighbors)
            {
                if (neighbor.Value.Label == node2.Label)
                {
                    findNode2 = true;
                }
                if (neighbor.Value.Label == node3.Label)
                {
                    findNode3 = true;
                }
                if (neighbor.Value.Label == node4.Label)
                {
                    findNode4 = true;
                }
                if (findNode2 && findNode3 && findNode4)
                    return true;
            }
            return false;
        }

        #endregion Methods
    }
}
